{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[-1,  0,  0,  0,  0,  0,  0],\n",
       "        [ 0,  0,  1,  0,  0, -1,  0],\n",
       "        [ 0,  0, -1,  0,  0,  0,  0],\n",
       "        [ 1,  0,  1,  0,  0,  0,  0],\n",
       "        [-1,  0,  0,  0,  0,  0,  0],\n",
       "        [ 1,  1,  0,  0, -1,  1,  0],\n",
       "        [ 0,  1,  0,  1,  1,  1,  0],\n",
       "        [ 0,  1,  0, -1,  1,  0,  0],\n",
       "        [ 0, -1,  1,  1,  1,  0,  1],\n",
       "        [ 1,  2,  2, -1,  2,  1,  1],\n",
       "        [ 2,  2,  2,  2,  2, -1,  1],\n",
       "        [ 2,  0, -1,  2,  2,  1,  1],\n",
       "        [-1,  1,  0,  1,  0,  0,  1],\n",
       "        [ 2,  1,  1,  1,  0,  0,  1],\n",
       "        [ 0,  1,  0,  0, -1,  1,  1],\n",
       "        [ 2,  0,  0,  2,  2,  0,  1],\n",
       "        [ 1, -1,  1,  1,  1,  0,  1]]),\n",
       " array([[ 2,  2,  2,  2,  2, -1,  1],\n",
       "        [ 2,  0, -1,  2,  2,  1,  1],\n",
       "        [-1,  1,  0,  1,  0,  0,  1],\n",
       "        [ 2,  1,  1,  1,  0,  0,  1],\n",
       "        [ 0,  1,  0,  0, -1,  1,  1],\n",
       "        [ 2,  0,  0,  2,  2,  0,  1],\n",
       "        [ 1, -1,  1,  1,  1,  0,  1]]))"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "#加载数据集\n",
    "def load_data():\n",
    "    with open('有缺失数据.txt') as fr:\n",
    "        lines = fr.readlines()\n",
    "\n",
    "    x = np.empty((len(lines), 7), dtype=int)\n",
    "\n",
    "    for i in range(len(lines)):\n",
    "        line = lines[i].strip().replace('?', '-1').split(',')\n",
    "        x[i] = line\n",
    "\n",
    "    test_x = x[10:]\n",
    "    #x = x[:10]\n",
    "\n",
    "    return x, test_x\n",
    "\n",
    "\n",
    "x, test_x = load_data()\n",
    "x, test_x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w = np.ones(len(x))\n",
    "w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[-1,  0,  0,  0,  0,  0,  0],\n",
       "        [ 0,  0,  1,  0,  0, -1,  0],\n",
       "        [ 0,  0, -1,  0,  0,  0,  0],\n",
       "        [ 1,  0,  1,  0,  0,  0,  0],\n",
       "        [-1,  0,  0,  0,  0,  0,  0],\n",
       "        [ 1,  1,  0,  0, -1,  1,  0],\n",
       "        [ 0,  1,  0,  1,  1,  1,  0],\n",
       "        [ 0,  1,  0, -1,  1,  0,  0],\n",
       "        [ 1,  2,  2, -1,  2,  1,  1],\n",
       "        [ 2,  2,  2,  2,  2, -1,  1],\n",
       "        [ 2,  0, -1,  2,  2,  1,  1],\n",
       "        [-1,  1,  0,  1,  0,  0,  1],\n",
       "        [ 2,  1,  1,  1,  0,  0,  1],\n",
       "        [ 0,  1,  0,  0, -1,  1,  1],\n",
       "        [ 2,  0,  0,  2,  2,  0,  1]]),\n",
       " array([1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.]))"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_D_pi(_x, col, _w):\n",
    "    D_pi = _x[:, col] != -1\n",
    "    return _x[D_pi], _w[D_pi]\n",
    "\n",
    "\n",
    "D_pi, w_pi = get_D_pi(x, 1, w)\n",
    "D_pi, w_pi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8823529411764706"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#无缺子集占全集比例\n",
    "def get_p(_w, w_pi):\n",
    "    return w_pi.sum() / _w.sum()\n",
    "\n",
    "\n",
    "get_p(w, w_pi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4666666666666667"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#k类占无缺子集的比例\n",
    "def get_pk(D_pi, w_pi, k):\n",
    "    Dk_pi = D_pi[:, -1] == k\n",
    "    wk_pi = w_pi[Dk_pi]\n",
    "\n",
    "    return wk_pi.sum() / w_pi.sum()\n",
    "\n",
    "\n",
    "get_pk(D_pi, w_pi, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9967916319816366"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#计算数据集的熵\n",
    "def get_entropy(D_pi, w_pi):\n",
    "    entropy = 0\n",
    "    for k in [0, 1]:\n",
    "        pk = get_pk(D_pi, w_pi, k)\n",
    "        if pk == 0:\n",
    "            continue\n",
    "        entropy += pk * np.log2(pk)\n",
    "    return -entropy\n",
    "\n",
    "\n",
    "get_entropy(D_pi, w_pi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4666666666666667"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#v属性占无缺子集的比例\n",
    "def get_rv(D_pi, w_pi, col, v):\n",
    "    Dv_pi = D_pi[:, col] == v\n",
    "    wv_pi = w_pi[Dv_pi]\n",
    "\n",
    "    return wv_pi.sum() / w_pi.sum()\n",
    "\n",
    "\n",
    "get_rv(D_pi, w_pi, 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.2519658176560344"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#计算信息增益\n",
    "def get_gain(D_pi, w_pi, col, _w):\n",
    "\n",
    "    #列熵\n",
    "    col_entropy = 0\n",
    "\n",
    "    #根据列值,把数据分成n份\n",
    "    for v in set(D_pi[:, col]):\n",
    "        #v属性占无缺子集的比例\n",
    "        rv = get_rv(D_pi, w_pi, col, v)\n",
    "\n",
    "        #计算数据集的熵\n",
    "        v_pi = D_pi[:, col] == v\n",
    "        Dv_pi = D_pi[v_pi]\n",
    "        wv_pi = w_pi[v_pi]\n",
    "        entropy = get_entropy(Dv_pi, wv_pi)\n",
    "\n",
    "        #这个列的熵,等于这个式子的累计\n",
    "        col_entropy += rv * entropy\n",
    "\n",
    "    #信息增益,就是切分数据后,熵值能下降多少,这个值越大越好\n",
    "    gain = get_entropy(D_pi, w_pi) - col_entropy\n",
    "\n",
    "    #无缺子集占全集比例\n",
    "    p = get_p(_w, w_pi)\n",
    "\n",
    "    return p * gain\n",
    "\n",
    "\n",
    "D_pi, w_pi = get_D_pi(x, 0, w)\n",
    "get_gain(D_pi, w_pi, 0, w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_split_col(_x, _w):\n",
    "    best_col = -1\n",
    "    best_gain = 0\n",
    "\n",
    "    #遍历所有的列,最后一列是y,不需要计算\n",
    "    for col in range(_x.shape[1] - 1):\n",
    "\n",
    "        D_pi, w_pi = get_D_pi(_x, col, _w)\n",
    "\n",
    "        #信息增益,就是切分数据后,熵值能下降多少,这个值越大越好\n",
    "        gain = get_gain(D_pi, w_pi, col, _w)\n",
    "\n",
    "        #信息增益最大的列,就是要被拆分的列\n",
    "        if gain > best_gain:\n",
    "            best_gain = gain\n",
    "            best_col = col\n",
    "\n",
    "    return best_col\n",
    "\n",
    "\n",
    "get_split_col(x, w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node col=0\n",
      "Leaf y=1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(None, None)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#创建节点和叶子对象,用来构建树\n",
    "class Node():\n",
    "    def __init__(self, col, w):\n",
    "        self.col = col\n",
    "        self.children = {}\n",
    "        self.w = w\n",
    "\n",
    "    def __str__(self):\n",
    "        return 'Node col=%d' % self.col\n",
    "\n",
    "\n",
    "class Leaf():\n",
    "    def __init__(self, y):\n",
    "        self.y = y\n",
    "\n",
    "    def __str__(self):\n",
    "        return 'Leaf y=%d' % self.y\n",
    "\n",
    "\n",
    "print(Node(0, None)), print(Leaf(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=0 \n"
     ]
    }
   ],
   "source": [
    "#打印树的方法\n",
    "def print_tree(node, prefix='', subfix=''):\n",
    "    prefix += '-' * 4\n",
    "    print(prefix, node, subfix)\n",
    "    if isinstance(node, Leaf):\n",
    "        return\n",
    "    for i in node.children:\n",
    "        subfix = 'value=' + str(i)\n",
    "        print_tree(node.children[i], prefix, subfix)\n",
    "\n",
    "\n",
    "print_tree(Node(0, None))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#先在所有数据上求最大信息增益的列,结果是3\n",
    "get_split_col(x, w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node col=3\n"
     ]
    }
   ],
   "source": [
    "#根据上面的结果,创建根节点,根节点根据列3的值来分割数据\n",
    "root = Node(3, w)\n",
    "print(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=3 \n",
      "-------- Node col=1 value=0\n",
      "-------- Node col=5 value=1\n",
      "-------- Leaf y=1 value=2\n"
     ]
    }
   ],
   "source": [
    "#添加子节点的方法\n",
    "def create_children(_x, parent_node):\n",
    "\n",
    "    #求非空子集\n",
    "    D_pi, w_pi = get_D_pi(_x, parent_node.col, parent_node.w)\n",
    "\n",
    "    #遍历父节点col列所有的取值\n",
    "    for split_value in np.unique(D_pi[:, parent_node.col]):\n",
    "        #首先根据父节点col列的取值分割数据\n",
    "        split = D_pi[:, parent_node.col] == split_value\n",
    "        sub_x = D_pi[split]\n",
    "        sub_w = w_pi[split]\n",
    "\n",
    "        #取去重y值\n",
    "        unique_y = np.unique(sub_x[:, -1])\n",
    "\n",
    "        #如果所有的y都是一样的,说明是个叶子节点\n",
    "        if len(unique_y) == 1:\n",
    "            parent_node.children[split_value] = Leaf(unique_y[0])\n",
    "            continue\n",
    "\n",
    "        #否则,是个分支节点,计算最佳切分列\n",
    "        split_col = get_split_col(sub_x, sub_w)\n",
    "\n",
    "        empty_x = _x[_x[:, parent_node.col] == -1]\n",
    "        p = get_p(w_pi, sub_w)\n",
    "        for _ in range(len(empty_x)):\n",
    "            sub_w = np.append(sub_w, p)\n",
    "\n",
    "        #添加分支节点到父节点上\n",
    "        parent_node.children[split_value] = Node(col=split_col, w=sub_w)\n",
    "\n",
    "\n",
    "create_children(x, root)\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=3 \n",
      "-------- Node col=1 value=0\n",
      "------------ Leaf y=0 value=0\n",
      "------------ Node col=0 value=1\n",
      "------------ Leaf y=1 value=2\n",
      "-------- Node col=5 value=1\n",
      "-------- Leaf y=1 value=2\n"
     ]
    }
   ],
   "source": [
    "#继续创建,3=0节点的下一层\n",
    "x_3_0 = x[np.logical_or(x[:, 3] == 0, x[:, 3] == -1)]\n",
    "create_children(x_3_0, root.children[0])\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=3 \n",
      "-------- Node col=1 value=0\n",
      "------------ Leaf y=0 value=0\n",
      "------------ Node col=0 value=1\n",
      "---------------- Node col=5 value=0\n",
      "---------------- Leaf y=0 value=1\n",
      "------------ Leaf y=1 value=2\n",
      "-------- Node col=5 value=1\n",
      "-------- Leaf y=1 value=2\n"
     ]
    }
   ],
   "source": [
    "#继续创建,3=0,1=1的下一层\n",
    "x_3_0_and_1_1 = x_3_0[np.logical_or(x_3_0[:, 1] == 1, x_3_0[:, 1] == -1)]\n",
    "create_children(x_3_0_and_1_1, root.children[0].children[1])\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=3 \n",
      "-------- Node col=1 value=0\n",
      "------------ Leaf y=0 value=0\n",
      "------------ Node col=0 value=1\n",
      "---------------- Node col=5 value=0\n",
      "-------------------- Leaf y=0 value=0\n",
      "-------------------- Leaf y=1 value=1\n",
      "---------------- Leaf y=0 value=1\n",
      "------------ Leaf y=1 value=2\n",
      "-------- Node col=5 value=1\n",
      "-------- Leaf y=1 value=2\n"
     ]
    }
   ],
   "source": [
    "#继续创建,3=0,1=1,0=0的下一层\n",
    "x_3_0_and_1_1_and_0_0 = x_3_0_and_1_1[np.logical_or(x_3_0_and_1_1[:, 0] == 0,\n",
    "                                                    x_3_0_and_1_1[:, 0] == -1)]\n",
    "create_children(x_3_0_and_1_1_and_0_0,\n",
    "                root.children[0].children[1].children[0])\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=3 \n",
      "-------- Node col=1 value=0\n",
      "------------ Leaf y=0 value=0\n",
      "------------ Node col=0 value=1\n",
      "---------------- Node col=5 value=0\n",
      "-------------------- Leaf y=0 value=0\n",
      "-------------------- Leaf y=1 value=1\n",
      "---------------- Leaf y=0 value=1\n",
      "------------ Leaf y=1 value=2\n",
      "-------- Node col=5 value=1\n",
      "------------ Node col=2 value=0\n",
      "------------ Node col=0 value=1\n",
      "-------- Leaf y=1 value=2\n"
     ]
    }
   ],
   "source": [
    "#继续创建,3=1节点的下一层\n",
    "x_3_1 = x[np.logical_or(x[:, 3] == 1, x[:, 3] == -1)]\n",
    "create_children(x_3_1, root.children[1])\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=3 \n",
      "-------- Node col=1 value=0\n",
      "------------ Leaf y=0 value=0\n",
      "------------ Node col=0 value=1\n",
      "---------------- Node col=5 value=0\n",
      "-------------------- Leaf y=0 value=0\n",
      "-------------------- Leaf y=1 value=1\n",
      "---------------- Leaf y=0 value=1\n",
      "------------ Leaf y=1 value=2\n",
      "-------- Node col=5 value=1\n",
      "------------ Node col=2 value=0\n",
      "---------------- Node col=4 value=0\n",
      "---------------- Leaf y=1 value=1\n",
      "------------ Node col=0 value=1\n",
      "---------------- Leaf y=0 value=0\n",
      "---------------- Leaf y=1 value=1\n",
      "-------- Leaf y=1 value=2\n"
     ]
    }
   ],
   "source": [
    "#继续创建,3=1,5=0节点的下一层\n",
    "#继续创建,3=1,5=1节点的下一层\n",
    "x_3_1_and_5_0 = x_3_1[np.logical_or(x_3_1[:, 5] == 0, x_3_1[:, 5] == -1)]\n",
    "x_3_1_and_5_1 = x_3_1[np.logical_or(x_3_1[:, 5] == 1, x_3_1[:, 5] == -1)]\n",
    "create_children(x_3_1_and_5_0, root.children[1].children[0])\n",
    "create_children(x_3_1_and_5_1, root.children[1].children[1])\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=3 \n",
      "-------- Node col=1 value=0\n",
      "------------ Leaf y=0 value=0\n",
      "------------ Node col=0 value=1\n",
      "---------------- Node col=5 value=0\n",
      "-------------------- Leaf y=0 value=0\n",
      "-------------------- Leaf y=1 value=1\n",
      "---------------- Leaf y=0 value=1\n",
      "------------ Leaf y=1 value=2\n",
      "-------- Node col=5 value=1\n",
      "------------ Node col=2 value=0\n",
      "---------------- Node col=4 value=0\n",
      "-------------------- Leaf y=1 value=0\n",
      "-------------------- Leaf y=0 value=1\n",
      "---------------- Leaf y=1 value=1\n",
      "------------ Node col=0 value=1\n",
      "---------------- Leaf y=0 value=0\n",
      "---------------- Leaf y=1 value=1\n",
      "-------- Leaf y=1 value=2\n"
     ]
    }
   ],
   "source": [
    "#继续创建,3=1,5=0,2=0节点的下一层\n",
    "x_3_1_and_5_0_and_2_0 = x_3_1_and_5_0[np.logical_or(x_3_1_and_5_0[:, 2] == 0,\n",
    "                                                    x_3_1_and_5_0[:, 2] == -1)]\n",
    "create_children(x_3_1_and_5_0_and_2_0,\n",
    "                root.children[1].children[0].children[0])\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n"
     ]
    }
   ],
   "source": [
    "#预测方法,测试\n",
    "def pred(_x, node):\n",
    "    col_value = _x[node.col]\n",
    "    node = node.children[col_value]\n",
    "\n",
    "    if isinstance(node, Leaf):\n",
    "        return node.y\n",
    "\n",
    "    return pred(_x, node)\n",
    "\n",
    "\n",
    "correct = 0\n",
    "all_x = x[(x != -1).all(axis=1)]\n",
    "for i in all_x:\n",
    "    if pred(i, root) == i[-1]:\n",
    "        correct += 1\n",
    "\n",
    "print(correct / len(all_x))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
